package 剪绳子;

public class Solution
{
    public int cutRope(int target)
    {
        //贪心算法
        //长度>=5时取分割3，==4时分割2
        if (target<2)
            return 0;
        if (target==2)
            return 1;
        if (target==3)
            return 2;
        int numOf3=target/3;

        if (target-(numOf3*3)==1)
            numOf3--;
        int numOf2=(target-numOf3*3)/2;
        return (int)(Math.pow(3,numOf3)*Math.pow(2,numOf2));
    }
    //动态规划

    public int cutRope1(int n)
    {
        // n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2,
        if(n==2)
            return 1;
        if(n==3)
            return 2;
        int[] dp = new int[n+1];
        /*
        下面3行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3，
        这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。
         */
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        int res=0;//记录最大的
        for (int i = 4; i <= n; i++)
        {
            for (int j = 1; j <=i/2 ; j++)
            {
                res=Math.max(res,dp[j]*dp[i-j]);
            }
            dp[i]=res;
        }
        return dp[n];
    }
}
